// https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

#include <iostream>

using namespace std;
 
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
		if(!head || !head->next){
			return head;
		}
		ListNode* dummy = new ListNode(-1);
		ListNode* prev = dummy;
		dummy->next = head;
		while(head->next){
			if(head->val == head->next->val){
				ListNode * tmp = head->next;
				// 判定相同元素，并删除
				while(tmp->next && tmp->val == tmp->next->val){
					ListNode * tmpNext = tmp->next;
					delete(tmp);
					tmp = tmpNext;
				}
				delete(head);
				head = tmp->next;
				prev->next = head;
				delete(tmp);
				// 如果最后一个元素也是相同的，则跳出循环 
				if(!head) break;
			}else{
				prev = head;
				head = head->next;
			}
		}
		return dummy->next;
    }
	
	ListNode * init(int n){
		ListNode * head = new ListNode(1);
		ListNode * index = head;
		for(int i = 1; i <= 1; i++){
			ListNode * tmp = new ListNode(i);
			index->next = tmp;
			index = index->next;
		}
		return head;
	}
	
	void show(ListNode * head){
		while(head){
			cout << head->val << ",";
			head = head->next;
		}
		cout << endl;
	}
};

int main(){
	Solution so;
	ListNode * head = so.init(2);
	so.show(head);
	ListNode * newHead = so.deleteDuplicates(head);
	cout << "new: " << endl;
	so.show(newHead);
	return 0;
	
}